package com.example.demo.arithmetic.datastructure.tree;

import java.util.Arrays;

/**
 * 给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value
 * ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。
 * 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。
 * <p>
 * 注意，可能存在多种有效的插入方式，
 * 只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。
 */
public class Leetcode701 {

    public TreeNode insertIntoBST(TreeNode root, int val) {
        TreeNode node = root;
        // 先查找 有的话更新
        TreeNode parent = null;
        while (node != null) {
            parent = node;
            if (val < node.val) {
                node = node.left;
            } else if (val > node.val) {
                node = node.right;
            }
        }
        if (parent == null) {
            root = new TreeNode(val);
            return root;
        }
        // 没找到 新增
        TreeNode newNode = new TreeNode(val);
        if (parent.val > newNode.val) {
            parent.left = newNode;
        } else if (parent.val < newNode.val) {
            parent.right = newNode;
        }
        return root;
    }

    public TreeNode insertIntoBST2(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }
        TreeNode pos = root;
        while (pos != null) {
            if (val < pos.val) {
                if (pos.left == null) {
                    pos.left = new TreeNode(val);
                    break;
                } else {
                    pos = pos.left;
                }
            } else {
                if (pos.right == null) {
                    pos.right = new TreeNode(val);
                    break;
                } else {
                    pos = pos.right;
                }
            }
        }
        return root;

//        作者：力扣官方题解
//        链接：https://leetcode.cn/problems/insert-into-a-binary-search-tree/solutions/432223/er-cha-sou-suo-shu-zhong-de-cha-ru-cao-zuo-by-le-3/
//        来源：力扣（LeetCode）
//        著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
    }

    /**
     * 递归实现
     *
     * @param root
     * @param val  5
     *             / \
     *             2   6
     *             / \   \
     *             1   3   7
     * @return
     */
    public TreeNode insertIntoBST3(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }
        if (val < root.val) {
            root.left = insertIntoBST3(root.left, val);
        } else {
            root.right = insertIntoBST3(root.right, val);
        }
        return root;
    }

    public static void main(String[] args) {
        TreeNode n1 = new TreeNode(1);
        TreeNode n3 = new TreeNode(3);
        TreeNode n2 = new TreeNode(2, n1, n3);

        TreeNode n5 = new TreeNode(5);
        TreeNode n7 = new TreeNode(7);
        TreeNode n6 = new TreeNode(6, n5, n7);
        TreeNode root = new TreeNode(4, n2, n6);

        TreeNode treeNode = new Leetcode701().insertIntoBST(root, 8);
        // 打印
        System.out.println(treeNode);
    }
}
